package edu.dayu.demo1;

/**
 * 输入：n = 4, index = 2,  maxSum = 6
 * 输出：2
 * 解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
 * 思路：1、首先我们并不需要把整个数组算出来，题目只需要得到一个数
 *      2、这个数肯定在 1-maxSum 之间，所以用二分法来找这个数。
 *      3、假设 index 位置是 temp ，然后计算 temp 两边+temp 的值，temp两边可以按 方差为 1 的递减数列来计算；
 */
public class 前n个数字二进制中1的个数 {
    public static void main(String[] args) {
        int n = 6, index = 2,  maxSum = 931384943;
        System.out.println(maxIndex(n,index,maxSum));
    }

    public static int maxIndex(int n,int index,int maxSum){
        int left = 1;
        int right = maxSum;
        while (left<right){
            int temp = (left+right+1)/2;
            long sum = temp+vail(index,temp)+vail(n-index-1,temp);
            if (sum<=maxSum){
                left = temp;
            }else{
                right = temp-1;
            }
        }
        return left;
    }

    /**
     * 通过给 长度 计算方差为1的数列，
     */
    public static long vail(int index,int temp){
        long sum = 0;
        // 长度小于等于 最后一个数，说明不同补 1
        if (index+1<=temp){
            sum = (long) ((temp - index) + temp - 1) *index/2;
        }else {
            sum = index-temp+1+ (long) temp *(temp-1)/2;
        }
        return sum;
    }
}
